0% completed
Problem Statement
You are given a positive integer n. You are also given undirected graph containing 0 to n - 1 nodes, and 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.
Return the count of unique node pairs where there's no path from one node to another.
Examples
Example 1:
- Input:
n = 4, edges = [[0, 1], [2, 3]]
- Expected Output: 4
- Justification: The graph is divided into two disconnected parts: nodes 0 and 1 are connected, and nodes 2 and 3 are connected. The unreachable pairs are (0, 2), (0, 3), (1, 2), and (1, 3).
Example 2:
- Input:
n = 5, edges = [[0, 1], [2, 3]]
- Expected Output: 8
- Justification: The unreachable pairs are (0, 2), (0, 3), (1, 2), (1, 3), (0, 4), (1, 4), (2, 4), and (3, 4).
Example 3:
- Input:
n = 3, edges = []
- Expected Output: 3
- Justification: With no edges, every node is isolated. Hence, all possible pairs are unreachable from each other: (0, 1), (0, 2), and (1, 2).
Solution
To solve this problem, we'll leverage depth-first search (DFS) to identify all connected components within the graph. By knowing the size of each connected component, we can calculate how many pairs of nodes within the same component can reach each other. Since the problem asks for unreachable pairs, we'll subtract the count of reachable pairs from the total possible pairs in the graph.
This approach is effective because it directly identifies the sizes of isolated sections in the graph, making it straightforward to compute the unreachable pairs by using combinatorial mathematics. The use of DFS ensures that we can efficiently traverse and mark all nodes in a connected component, thereby accurately calculating each component's size.
Step-by-Step Algorithm with Detailed DFS Steps
-
Initialize Data Structures:
- Create a
HashMapcalledadjto store the adjacency list of the graph. This map associates each node with a list of its neighbors. - Initialize a
booleanarray namedvisitwith a length ofn(the number of nodes), with all elements set tofalse. This array tracks which nodes have been visited during DFS traversals.
- Create a
-
Build the Graph (Adjacency List):
- For each edge
[u, v]in theedgesarray, do the following:- Add
vto the adjacency list ofuanduto the adjacency list ofv. This step ensures that the graph correctly represents all connections (edges) between nodes.
- Add
- For each edge
-
Depth-First Search (DFS) to Find Component Sizes:
- Define a recursive method
dfsthat takes a nodenode, the adjacency listadj, and the visited arrayvisit. This method returns the size of the connected component that includesnode. - Initialize a local variable
countto 1, representing the current node. - Inside
dfs, marknodeas visited (visit[node] = true). - For each neighbor of
node(accessible viaadj.get(node)), if the neighbor has not been visited (!visit[neighbor]), recursively calldfson the neighbor and add the result tocount. - Return
countat the end ofdfs, representing the total size of the connected component found.
- Define a recursive method
-
Calculate Unreachable Pairs:
- Initialize two long variables:
numberOfPairsto store the final result, andremainingNodesto track the number of nodes not yet included in any connected component, initially set ton. - Iterate over all nodes
ifrom 0 ton - 1. For each nodei:- If
visit[i]isfalse(nodeihas not been visited), call thedfsmethod starting fromi. This call explores the entire connected component containingi, marks all nodes within it as visited, and returns the size of this component. - Use the size returned by
dfsto updatenumberOfPairs. The formulanumberOfPairs += sizeOfComponent * (remainingNodes - sizeOfComponent)calculates the number of new unreachable pairs formed by the current component and updatesnumberOfPairsaccordingly. - Subtract the size of the current component from
remainingNodesto reflect the reduced number of nodes available for forming pairs.
- If
- Initialize two long variables:
-
Return the Total Number of Unreachable Pairs:
- After iterating through all nodes and calculating unreachable pairs for each component, return
numberOfPairsas the final result. This value represents the total number of pairs of nodes in the graph that cannot reach each other.
- After iterating through all nodes and calculating unreachable pairs for each component, return
Algorithm Walkthrough
Let's consider the input: n = 5, edges = [[0, 1], [2, 3]].
-
Initialization:
adjis an empty map, andvisitis an array offalsevalues of length 5.
-
Build the Graph:
- Add edge [0, 1] to
adj:adj[0]now includes 1, andadj[1]includes 0. - Add edge [2, 3] to
adj:adj[2]now includes 3, andadj[3]includes 2.
- Add edge [0, 1] to
-
Count Unreachable Pairs:
- Start with
i = 0,numberOfPairs = 0, andremainingNodes = 5. - Since
visit[0]isfalse, perform DFS from node 0:- Visit nodes 0 and 1, marking them as visited. The DFS returns 2, the size of this component.
- Update
numberOfPairs += 2 * (5 - 2) = 6. - Update
remainingNodes -= 2, nowremainingNodes = 3.
- Continue with
i = 1toi = 2. Node 1 is already visited, so move to node 2:- Perform DFS from node 2, visiting nodes 2 and 3. The DFS returns 2.
- Update
numberOfPairs += 2 * (3 - 2) = 2. - Update
remainingNodes -= 2, nowremainingNodes = 1.
- For
i = 3andi = 4, nodes 3 is already visited, and wheni = 4, no DFS is performed as it's disconnected from others, implicitly counting as a single-node component that doesn't add tonumberOfPairssince its potential pairs have already been counted.
- Start with
-
Return Result:
- The total
numberOfPairsis (6 + 2 = 8), which is the final result returned by the method.
- The total
Code
Complexity Analysis
Time Complexity
- DFS Traversal: The depth-first search (DFS) is performed for each node that hasn't been visited yet. Since each edge is visited exactly twice (once for each direction in the undirected graph), the time complexity for the DFS part is
, where (V) is the number of vertices (nodes) and (E) is the number of edges in the graph. - Building the Adjacency List: The adjacency list is built by iterating through each edge once, leading to a time complexity of
for this step.
Overall, the time complexity of the algorithm is
Space Complexity
- Adjacency List: The space complexity for storing the adjacency list is
, as it needs to store a list of edges for each of the (V) vertices. - Visit Array: An additional
space is used to keep track of which nodes have been visited during DFS. - DFS Call Stack: In the worst-case scenario, the depth of the call stack could be
in the case of a deeply nested tree structure.
Hence, the total space complexity of the algorithm is
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm with Detailed DFS Steps
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity